{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Paths from Source Lead to Destination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leadsToDestination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从始点到终点的所有路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定有向图的边&nbsp;<code>edges</code>，以及该图的始点&nbsp;<code>source</code>&nbsp;和目标终点&nbsp;<code>destination</code>，确定从始点&nbsp;<code>source</code>&nbsp;出发的所有路径是否最终结束于目标终点&nbsp;<code>destination</code>，即：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从始点&nbsp;<code>source</code> 到目标终点&nbsp;<code>destination</code> 存在至少一条路径</li>\n",
    "\t<li>如果存在从始点&nbsp;<code>source</code> 到没有出边的节点的路径，则该节点就是路径终点。</li>\n",
    "\t<li>从始点<code>source</code>到目标终点&nbsp;<code>destination</code> 可能路径数是有限数字</li>\n",
    "</ul>\n",
    "\n",
    "<p>当从始点&nbsp;<code>source</code> 出发的所有路径都可以到达目标终点&nbsp;<code>destination</code> 时返回&nbsp;<code>true</code>，否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/03/21/485_example_1.png\" style=\"height: 208px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>说明：</strong>节点 1 和节点 2 都可以到达，但也会卡在那里。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/03/21/485_example_2.png\" style=\"height: 230px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>说明：</strong>有两种可能：在节点 3 处结束，或是在节点 1 和节点 2 之间无限循环。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/03/21/485_example_3.png\" style=\"height: 183px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= source &lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= destination &lt;= n - 1</code></li>\n",
    "\t<li>给定的图中可能带有自环和平行边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-paths-from-source-lead-to-destination](https://leetcode.cn/problems/all-paths-from-source-lead-to-destination/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-paths-from-source-lead-to-destination](https://leetcode.cn/problems/all-paths-from-source-lead-to-destination/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[0,2]]\\n0\\n2', '4\\n[[0,1],[0,3],[1,2],[2,1]]\\n0\\n3', '4\\n[[0,1],[0,2],[1,3],[2,3]]\\n0\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        # graph = [[] for _ in range(n)] #collections.defaultdict(list)\n",
    "\n",
    "        # for x, y in edges:\n",
    "        #     graph[x].append(y)\n",
    "        \n",
    "        # #vis = set()\n",
    "        # def dfs(ind, vis):\n",
    "        #     #nonlocal temp\n",
    "        #     if not graph[ind]:\n",
    "        #         return ind == destination\n",
    "            \n",
    "        #     vis.add(ind)\n",
    "        #     for nei in graph[ind]:\n",
    "        #         if nei in vis or not dfs(nei, vis):\n",
    "        #             return False\n",
    "        #     vis.remove(ind)\n",
    "        #     return True\n",
    "\n",
    "        # return dfs(source, set())\n",
    "\n",
    "        # dfs TLE\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # for src, dst in edges:\n",
    "        #     graph[src].append(dst)\n",
    "\n",
    "        # def dfs(cur, visited):\n",
    "        #     if not graph[cur]:\n",
    "        #         return cur == destination\n",
    "        #     visited.add(cur)\n",
    "        #     for nxt in graph[cur]:\n",
    "        #         if nxt in visited or not dfs(nxt, visited):\n",
    "        #             return False\n",
    "        #     visited.remove(cur)\n",
    "        #     return True\n",
    "        # return dfs(source, set())\n",
    "\n",
    "        # bfs\n",
    "        graph = [[] for _ in range(n)]\n",
    "        in_deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            graph[y].append(x)\n",
    "            in_deg[x] += 1\n",
    "        \n",
    "        if in_deg[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                cur = q.pop()\n",
    "                if cur == source:\n",
    "                    return True\n",
    "                \n",
    "                for nei in graph[cur]:\n",
    "                    in_deg[nei] -= 1\n",
    "                    if in_deg[nei] == 0:\n",
    "                        q.append(nei)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph[v].append(u)\n",
    "            indegree[u] += 1\n",
    "        \n",
    "        if indegree[destination]:\n",
    "            return False\n",
    "        \n",
    "        queue = [destination]\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            if curr == source:\n",
    "                return True\n",
    "            for node in graph[curr]:\n",
    "                if curr == node:\n",
    "                    return False\n",
    "                indegree[node] -= 1\n",
    "                if indegree[node] == 0:\n",
    "                    queue.append(node)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        in_degress = [0]*n\n",
    "        for u,v in edges:\n",
    "            g[v].append(u)\n",
    "            in_degress[u]+=1\n",
    "        if in_degress[destination]: return False\n",
    "\n",
    "        q = [destination]\n",
    "        while q:\n",
    "            x = q[0]\n",
    "            if x==source:\n",
    "                return True\n",
    "            q.pop(0)\n",
    "            for y in g[x]:\n",
    "                in_degress[y] -= 1\n",
    "                if in_degress[y] == 0:\n",
    "                    q.append(y)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0]*n\n",
    "        for i,j in edges:\n",
    "            graph[j].append(i)\n",
    "            # 反向入度(原图的出度)\n",
    "            degree[i] += 1\n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                # 稍微加速一下\n",
    "                if cur == new:\n",
    "                    return False\n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indegree = [0 for _ in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            indegree[edge[0]] += 1\n",
    "\n",
    "        q = deque()\n",
    "        if indegree[destination]:\n",
    "            return False\n",
    "        q.append(destination)\n",
    "\n",
    "        while q:\n",
    "            currNode = q.popleft()\n",
    "            if currNode == source:\n",
    "                return True\n",
    "\n",
    "            for node in graph[currNode]:\n",
    "                indegree[node] -= 1\n",
    "                if indegree[node] == 0:\n",
    "                    q.append(node)\n",
    "\n",
    "        return False        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0]*n\n",
    "        for i,j in edges:\n",
    "            graph[j].append(i)\n",
    "            # 反向入度(原图的出度)\n",
    "            degree[i] += 1\n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                # 稍微加速一下\n",
    "                if cur == new:\n",
    "                    return False\n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        e = [[] for _ in range(n)]\n",
    "        outdeg = [0] * n  \n",
    "        for edge in edges:  #反向\n",
    "            e[edge[1]].append(edge[0])\n",
    "            outdeg[edge[0]] += 1 \n",
    "        \n",
    "        if outdeg[destination]>0:\n",
    "            return False\n",
    "\n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        # source的出度=0时，进入，此时说明能从重点返回来\n",
    "        while len(q)>0:\n",
    "            now = q[0]\n",
    "            q = q[1:]\n",
    "            if now==source:\n",
    "                return True\n",
    "            for next in e[now]:\n",
    "                outdeg[next] -= 1\n",
    "                if outdeg[next]==0:\n",
    "                    q.append(next)\n",
    "        \n",
    "        return False\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        out = defaultdict(list)\n",
    "        indegree = [0]*n\n",
    "        for s,d in edges:\n",
    "            out[d].append(s)\n",
    "            indegree[s]+=1\n",
    "        if indegree[destination]:\n",
    "            return False\n",
    "        q = deque([destination])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node==source:\n",
    "                return True\n",
    "            for d in out[node]:\n",
    "                indegree[d]-=1\n",
    "                if indegree[d]==0:\n",
    "                    q.append(d)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        edges_dic = defaultdict(list)\n",
    "        visited = [0]*n\n",
    "        for f,t in edges:\n",
    "            edges_dic[t].append(f)\n",
    "            visited[f] += 1\n",
    "        #print(edges_dic,visited)\n",
    "        if visited[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            key = queue.popleft()\n",
    "            if key == source:\n",
    "                return True\n",
    "            for u in edges_dic[key]:\n",
    "                if u == key:\n",
    "                    #print(f'重复路径')\n",
    "                    return False\n",
    "                visited[u] -= 1\n",
    "                if visited[u] == 0:\n",
    "                    queue.append(u)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0]*n\n",
    "        for i,j in edges:\n",
    "            graph[j].append(i)\n",
    "            # 反向入度(原图的出度)\n",
    "            degree[i] += 1\n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                # 稍微加速一下\n",
    "                if cur == new:\n",
    "                    return False\n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        degree = [0] * n\n",
    "\n",
    "        for i, j in edges:\n",
    "            graph[j].append(i)\n",
    "            degree[i] += 1\n",
    "        \n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        \n",
    "        queue = deque([destination])\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                if cur == new:\n",
    "                    return False\n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        degree = [0] * n\n",
    "\n",
    "        for i, j in edges:\n",
    "            graph[j].append(i)\n",
    "            degree[i] += 1\n",
    "        \n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        \n",
    "        queue = deque([destination])\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                if cur == new:\n",
    "                    return False\n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        record = collections.defaultdict(list)\n",
    "        indegree = [0 for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            record[edge[1]].append(edge[0])\n",
    "            indegree[edge[0]] += 1\n",
    "        \n",
    "        if indegree[destination] != 0:\n",
    "            return False\n",
    "\n",
    "        queue = [destination]\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node == source:\n",
    "                return True\n",
    "            for nxt in record[node]:\n",
    "                if nxt == node:\n",
    "                    return False\n",
    "                indegree[nxt] -= 1\n",
    "                if indegree[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        edges_dic = defaultdict(list)\n",
    "        visited = [0]*n\n",
    "        for f,t in edges:\n",
    "            edges_dic[t].append(f)\n",
    "            visited[f] += 1\n",
    "        #print(visited)\n",
    "        if visited[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            key = queue.popleft()\n",
    "            if key == source:\n",
    "                return True\n",
    "            for u in edges_dic[key]:\n",
    "                \n",
    "                visited[u] -= 1\n",
    "                if visited[u] == 0:\n",
    "                    queue.append(u)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph[v].append(u)\n",
    "            indegree[u] += 1\n",
    "        \n",
    "        if indegree[destination]:\n",
    "            return False\n",
    "        \n",
    "        queue = [destination]\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            if curr == source:\n",
    "                return True\n",
    "            for node in graph[curr]:\n",
    "                if curr == node:\n",
    "                    return False\n",
    "                indegree[node] -= 1\n",
    "                if indegree[node] == 0:\n",
    "                    queue.append(node)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        # graph = [[] for _ in range(n)] #collections.defaultdict(list)\n",
    "\n",
    "        # for x, y in edges:\n",
    "        #     graph[x].append(y)\n",
    "        \n",
    "        # #vis = set()\n",
    "        # def dfs(ind, vis):\n",
    "        #     #nonlocal temp\n",
    "        #     if not graph[ind]:\n",
    "        #         return ind == destination\n",
    "            \n",
    "        #     vis.add(ind)\n",
    "        #     for nei in graph[ind]:\n",
    "        #         if nei in vis or not dfs(nei, vis):\n",
    "        #             return False\n",
    "        #     vis.remove(ind)\n",
    "        #     return True\n",
    "\n",
    "        # return dfs(source, set())\n",
    "\n",
    "        # dfs TLE\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # for src, dst in edges:\n",
    "        #     graph[src].append(dst)\n",
    "\n",
    "        # def dfs(cur, visited):\n",
    "        #     if not graph[cur]:\n",
    "        #         return cur == destination\n",
    "        #     visited.add(cur)\n",
    "        #     for nxt in graph[cur]:\n",
    "        #         if nxt in visited or not dfs(nxt, visited):\n",
    "        #             return False\n",
    "        #     visited.remove(cur)\n",
    "        #     return True\n",
    "        # return dfs(source, set())\n",
    "\n",
    "        # bfs\n",
    "        graph = [[] for _ in range(n)]\n",
    "        in_deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            graph[y].append(x)\n",
    "            in_deg[x] += 1\n",
    "        \n",
    "        if in_deg[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                cur = q.pop()\n",
    "                if cur == source:\n",
    "                    return True\n",
    "                \n",
    "                for nei in graph[cur]:\n",
    "                    in_deg[nei] -= 1\n",
    "                    if in_deg[nei] == 0:\n",
    "                        q.append(nei)\n",
    "        \n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        edges_dic = defaultdict(list)\n",
    "        visited = [0]*n\n",
    "        for f,t in edges:\n",
    "            edges_dic[t].append(f)\n",
    "            visited[f] += 1\n",
    "        if visited[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            key = queue.popleft()\n",
    "            if key == source:\n",
    "                return True\n",
    "            for u in edges_dic[key]:\n",
    "                #if key == u:\n",
    "                #    return False\n",
    "                visited[u] -= 1\n",
    "                if visited[u] == 0:\n",
    "                    queue.append(u)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0]*n\n",
    "        for i,j in edges:\n",
    "            graph[j].append(i)\n",
    "            degree[i] +=1\n",
    "        if degree[destination]:\n",
    "            return False\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur== source:\n",
    "                return True\n",
    "            for new in graph[cur]:\n",
    "                if cur==new:\n",
    "                    return False\n",
    "                degree[new] -=1\n",
    "                if degree[new]==0:\n",
    "                    queue.appendleft(new)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "        if len(g[destination])>0:return False\n",
    "        vis=[0]*n\n",
    "        @cache\n",
    "        def dfs(k):\n",
    "            if k==destination:return True\n",
    "            if len(g[k])==0:return False\n",
    "            for nk in g[k]:\n",
    "                if vis[nk]==1:return False\n",
    "                vis[nk]=1\n",
    "                if not dfs(nk):\n",
    "                    return False\n",
    "                vis[nk]=0\n",
    "            return True\n",
    "        return dfs(source)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        from collections import defaultdict, deque\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        degrees = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            graph[y].append(x)\n",
    "            degrees[x] += 1\n",
    "\n",
    "        if degrees[destination] != 0:\n",
    "            return False\n",
    "\n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            head = queue.popleft()\n",
    "            if head == source:\n",
    "                return True\n",
    "\n",
    "            for neighbor in graph[head]:\n",
    "                degrees[neighbor] -= 1\n",
    "                if degrees[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "        for i, j in edges:\n",
    "            graph[j].append(i)\n",
    "            degree[i] += 1\n",
    "        if degree[destination]:\n",
    "            return False \n",
    "        queue = deque([destination])\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur == source:\n",
    "                return True \n",
    "            for new in graph[cur]:\n",
    "                if cur == new:\n",
    "                    return False \n",
    "                degree[new] -= 1\n",
    "                if degree[new] == 0:\n",
    "                    queue.appendleft(new)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        degree = [0] * n\n",
    "        graph = {_: [] for _ in range(n)}\n",
    "        for i, j in edges:\n",
    "            degree[i] += 1\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        if degree[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for i in graph[cur]:\n",
    "                degree[i] -= 1\n",
    "                if degree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            if node==destination:\n",
    "                return True\n",
    "            if not graphdict[node] and node!=destination:\n",
    "                return False\n",
    "            visited[node]=True\n",
    "            for i in graphdict[node]:\n",
    "                if visited[i]:\n",
    "                    return False\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "            visited[node]=False\n",
    "            return True\n",
    "            \n",
    "        graphdict = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            if edge[0]==destination:\n",
    "                return False\n",
    "            graphdict[edge[0]].append(edge[1])\n",
    "        visited = [False for i in range(n)]\n",
    "\n",
    "        return dfs(source)\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        in_degress = [0]*n\n",
    "        for u,v in edges:\n",
    "            g[v].append(u)\n",
    "            in_degress[u]+=1\n",
    "        if in_degress[destination]: return False\n",
    "\n",
    "        q = [destination]\n",
    "        while q:\n",
    "            x = q[0]\n",
    "            if x==source:\n",
    "                return True\n",
    "            q.pop(0)\n",
    "            for y in g[x]:\n",
    "                in_degress[y] -= 1\n",
    "                if in_degress[y] == 0:\n",
    "                    q.append(y)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        cnt = Counter()\n",
    "        for x, y in edges:\n",
    "            g[y].append(x)\n",
    "            cnt[x] += 1\n",
    "        \n",
    "        if cnt[destination]:\n",
    "            return False\n",
    "        \n",
    "        q = deque([destination])\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for nxt in g[cur]:\n",
    "                if cur == nxt: return False\n",
    "                cnt[nxt] -= 1\n",
    "                if cnt[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        degree = [0] * n\n",
    "        graph = {_: [] for _ in range(n)}\n",
    "        for i, j in edges:\n",
    "            degree[i] += 1\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        if degree[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for i in graph[cur]:\n",
    "                if i in graph[i]:\n",
    "                    return False\n",
    "                degree[i] -= 1\n",
    "                if degree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "\n",
    "        def dfs(node):\n",
    "            if node==destination:\n",
    "                return True\n",
    "            if not graphdict[node] and node!=destination:\n",
    "                return False\n",
    "            visited[node]=True\n",
    "            for i in graphdict[node]:\n",
    "                if memorization[i]:\n",
    "                    continue\n",
    "                if visited[i]:\n",
    "                    return False\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "                memorization[i]=True\n",
    "            visited[node]=False\n",
    "            return True\n",
    "            \n",
    "        graphdict = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            if edge[0]==destination:\n",
    "                return False\n",
    "            graphdict[edge[0]].append(edge[1])\n",
    "        visited = [False for i in range(n)]\n",
    "        memorization = [False for i in range(n)]\n",
    "        memorization[destination]=True\n",
    "\n",
    "        return dfs(source)\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        degree = [0] * n\n",
    "        graph = {_: [] for _ in range(n)}\n",
    "        for i, j in edges:\n",
    "            degree[i] += 1\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        if degree[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for i in graph[cur]:\n",
    "                if i == cur:\n",
    "                    return False\n",
    "                degree[i] -= 1\n",
    "                if degree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        degree = [0] * n\n",
    "        graph = {_: [] for _ in range(n)}\n",
    "        for i, j in edges:\n",
    "            degree[i] += 1\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        if degree[destination] != 0:\n",
    "            return False\n",
    "        \n",
    "        q = []\n",
    "        q.append(destination)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur == source:\n",
    "                return True\n",
    "            for i in graph[cur]:\n",
    "                # if i in graph[i]:\n",
    "                #     return False\n",
    "                degree[i] -= 1\n",
    "                if degree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            graph[a].append(b)\n",
    "        \n",
    "        # if destination in graph:\n",
    "        #     return False\n",
    "\n",
    "        visited = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(node, tgt):\n",
    "            if node not in graph:\n",
    "                if node == tgt:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if visited[node] == 0:\n",
    "                visited[node] = 1\n",
    "            elif visited[node] == 1:\n",
    "                return False\n",
    "\n",
    "            for i in graph[node]:\n",
    "                if visited[i] != 2:\n",
    "                    if not dfs(i, tgt):\n",
    "                        return False\n",
    "            visited[node] = 2\n",
    "            return True\n",
    "        \n",
    "        return dfs(source, destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mem=None # 'u'=未访问, 'v'=在栈中, True, False\n",
    "    net=None\n",
    "    def f(self, s, d):\n",
    "        if s==d: \n",
    "            return True\n",
    "        if d in self.mem[s]:\n",
    "            if self.mem[s][d]==True or self.mem[s][d]==False:\n",
    "                return self.mem[s][d]\n",
    "            if self.mem[s][d]=='v':\n",
    "                return False\n",
    "                \n",
    "        self.mem[s][d]='v'\n",
    "\n",
    "        c = 0  #s后继与d连通的数量\n",
    "        for nb in self.net[s]:\n",
    "            if self.f( nb, d) : \n",
    "                c+=1\n",
    "            else:\n",
    "                break\n",
    "        res =(c>0 and c==len( self.net[s]) )\n",
    "        self.mem[s][d]=res\n",
    "        return res\n",
    "\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], s: int, d: int) -> bool:\n",
    "        self.mem = [ dict() for _ in range(n)]\n",
    "        self.net  = {  x:[] for x in range(n)  }\n",
    "        for a, b in edges:\n",
    "            self.net[a].append(b)\n",
    "            if a==d: # d不能有后继\n",
    "                return False\n",
    "        return self.f( s, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        # 邻接表表示图\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for src, dst in edges:\n",
    "            graph[src].append(dst)\n",
    "        # 取出source可达的所有点\n",
    "        s = set()\n",
    "        queue = deque()\n",
    "        queue.appendleft(source)\n",
    "        while queue:\n",
    "            curr = queue.pop()\n",
    "            if curr in s: continue\n",
    "            s.add(curr)\n",
    "            for num in graph[curr]:\n",
    "                if num not in s:\n",
    "                    queue.appendleft(num)\n",
    "        # 针对source的可达区域做拓扑排序\n",
    "        lst = []\n",
    "        ind, nxd = {}, {}\n",
    "        for i in range(n):\n",
    "            ind[i] = 0\n",
    "            nxd[i] = []\n",
    "        for edge in edges:\n",
    "            if edge[0] in s:\n",
    "                ind[edge[1]] += 1\n",
    "                nxd[edge[0]].append(edge[1])\n",
    "        dq = deque()\n",
    "        dq.appendleft(source)\n",
    "        while dq:\n",
    "            curr = dq.pop()\n",
    "            lst.append(curr)\n",
    "            # 遇到非destination的终点直接返回False\n",
    "            if not nxd[curr] and curr != destination:\n",
    "                return False\n",
    "            for node in nxd[curr]:\n",
    "                ind[node] -= 1\n",
    "                if ind[node] == 0:\n",
    "                    dq.appendleft(node)\n",
    "        # 可以完成拓扑排序则返回True\n",
    "        return len(lst) == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        # 邻接表表示图\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            d[i] = []\n",
    "        for edge in edges:\n",
    "            d[edge[0]].append(edge[1])\n",
    "        # 取出source可达的所有点\n",
    "        s = set()\n",
    "        queue = deque()\n",
    "        queue.appendleft(source)\n",
    "        while queue:\n",
    "            curr = queue.pop()\n",
    "            if curr in s: continue\n",
    "            s.add(curr)\n",
    "            for num in d[curr]:\n",
    "                if num not in s:\n",
    "                    queue.appendleft(num)\n",
    "        # 针对source的可达区域做拓扑排序\n",
    "        lst = []\n",
    "        ind, nxd = {}, {}\n",
    "        for i in range(n):\n",
    "            ind[i] = 0\n",
    "            nxd[i] = []\n",
    "        for edge in edges:\n",
    "            if edge[0] in s:\n",
    "                ind[edge[1]] += 1\n",
    "                nxd[edge[0]].append(edge[1])\n",
    "        dq = deque()\n",
    "        dq.appendleft(source)\n",
    "        while dq:\n",
    "            curr = dq.pop()\n",
    "            lst.append(curr)\n",
    "            # 遇到非destination的终点直接返回False\n",
    "            if not nxd[curr] and curr != destination:\n",
    "                return False\n",
    "            for node in nxd[curr]:\n",
    "                ind[node] -= 1\n",
    "                if ind[node] == 0:\n",
    "                    dq.appendleft(node)\n",
    "        # 可以完成拓扑排序则返回True\n",
    "        return len(lst) == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph_rev = [[] for _ in range(n)]\n",
    "        depended = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph_rev[v].append(u)\n",
    "            depended[u] += 1\n",
    "        if depended[destination]:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if i != destination and depended[i] == 0:\n",
    "                depended[i] += 1\n",
    "        def dfs(u):\n",
    "            if u == source:\n",
    "                return True\n",
    "            else:\n",
    "                for v in graph_rev[u]:\n",
    "                    depended[v] -= 1\n",
    "                    if not depended[v]:\n",
    "                        if dfs(v):\n",
    "                            return True\n",
    "                return False\n",
    "        return dfs(destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        visited=dict()\n",
    "        graph=[]\n",
    "        for _ in range(n):\n",
    "            graph.append([])\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "        path=set()\n",
    "        def dfs(now):\n",
    "            if now==destination:\n",
    "                return True\n",
    "            if now in visited:\n",
    "                return visited[now]\n",
    "            if now in path or len(graph[now])==0:\n",
    "                return False\n",
    "            path.add(now)\n",
    "            res=True\n",
    "            for e in graph[now]:\n",
    "                res&=dfs(e)\n",
    "            visited[now]=res\n",
    "            path.remove(now)\n",
    "            return res\n",
    "        if len(graph[destination])!=0:\n",
    "            return False\n",
    "        return dfs(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph_rev = [[] for _ in range(n)]\n",
    "        depended = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph_rev[v].append(u)\n",
    "            depended[u] += 1\n",
    "        if depended[destination]:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if i != destination and depended[i] == 0:\n",
    "                depended[i] += 1\n",
    "        def dfs(u):\n",
    "            if u == source:\n",
    "                return True\n",
    "            else:\n",
    "                for v in graph_rev[u]:\n",
    "                    depended[v] -= 1\n",
    "                    if not depended[v]:\n",
    "                        if dfs(v):\n",
    "                            return True\n",
    "                return False\n",
    "        return dfs(destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = [[] for i in range(n)]\n",
    "        depended = [0] * n\n",
    "\n",
    "        for u,v in edges:\n",
    "            g[v].append(u)\n",
    "            depended[u] += 1\n",
    "        \n",
    "        if depended[destination]:\n",
    "            return False\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != destination and depended[i] == 0:\n",
    "                depended[i] = 1\n",
    "\n",
    "        def dfs(node):\n",
    "            if node == source:\n",
    "                return True\n",
    "\n",
    "            for u in g[node]:\n",
    "                depended[u] -= 1\n",
    "                if not depended[u]:\n",
    "                    if dfs(u):\n",
    "                        return True\n",
    "            return False\n",
    "            \n",
    "        return dfs(destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        visited=dict()\n",
    "        graph=[]\n",
    "        for _ in range(n):\n",
    "            graph.append([])\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "        path=set()\n",
    "        def dfs(now):\n",
    "            if now==destination:\n",
    "                return True\n",
    "            if now in visited:\n",
    "                return visited[now]\n",
    "            if now in path or len(graph[now])==0:\n",
    "                visited[now]=False\n",
    "                return False\n",
    "            path.add(now)\n",
    "            res=True\n",
    "            for e in graph[now]:\n",
    "                res&=dfs(e)\n",
    "            visited[now]=res\n",
    "            path.remove(now)\n",
    "            return res\n",
    "        if len(graph[destination])!=0:\n",
    "            return False\n",
    "        return dfs(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        graph_rev = [[] for _ in range(n)]\n",
    "        depended = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph_rev[v].append(u)\n",
    "            depended[u] += 1\n",
    "        if depended[destination]:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if i != destination and depended[i] == 0:\n",
    "                depended[i] += 1\n",
    "        def dfs(u):\n",
    "            if u == source:\n",
    "                return True\n",
    "            else:\n",
    "                for v in graph_rev[u]:\n",
    "                    depended[v] -= 1\n",
    "                    if not depended[v]:\n",
    "                        if dfs(v):\n",
    "                            return True\n",
    "                return False\n",
    "        return dfs(destination)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        R = range(n)\n",
    "        G = [[] for i in R]\n",
    "        for a, b in edges:\n",
    "            G[a].append(b)\n",
    "        \n",
    "        if G[destination]: return False\n",
    "        \n",
    "        vis = [False] * n\n",
    "        vis[source] = True\n",
    "        \n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n == destination: return True\n",
    "            if not G[n] and n != destination: return False\n",
    "            vis[n] = True\n",
    "            for m in G[n]:\n",
    "                if vis[m] or not dfs(m): return False\n",
    "            vis[n] = False\n",
    "            return True\n",
    "        \n",
    "        return dfs(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :param source:\n",
    "        :param destination:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        m1 = defaultdict(list)\n",
    "        m2 = defaultdict(int)\n",
    "        mq = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m2[i[0]] += 1\n",
    "            m1[i[1]].append(i[0])\n",
    "            mq[i[0]].append(i[1])\n",
    "        dq1 = deque()\n",
    "        dq1.append(source)\n",
    "        used = set()\n",
    "        while dq1:\n",
    "            cur1 = dq1.popleft()\n",
    "            if cur1 in used:\n",
    "                continue\n",
    "            used.add(cur1)\n",
    "            todo = mq.get(cur1, [])\n",
    "            for i in todo:\n",
    "                dq1.append(i)\n",
    "        m3,m4 = {}, {}\n",
    "        for i in m1:\n",
    "            if i in used:\n",
    "                m3[i] = m1[i]\n",
    "        for i in m2:\n",
    "            if i in used:\n",
    "                m4[i] = m2[i]\n",
    "        m1, m2 = m3, m4\n",
    "        st = SortedList(key=lambda x:x[0])\n",
    "        zcnt = 0\n",
    "        for i in used:\n",
    "            vv1 = m2.get(i, 0)\n",
    "            st.add((vv1,  i))\n",
    "            if vv1 == 0:\n",
    "                zcnt += 1\n",
    "        if zcnt != 1:\n",
    "            return False\n",
    "\n",
    "        if st[0][1] != destination:\n",
    "            return False\n",
    "        cur = st[0]\n",
    "        while len(st) > 0:\n",
    "            todol = []\n",
    "            while st and st[0][0] == 0:\n",
    "                v1 = st.pop(0)\n",
    "                todol.append(v1[1])\n",
    "            if len(st) == 0:\n",
    "                if len(todol) == 1 and todol[0] == source:\n",
    "                    return True\n",
    "            if len(todol) == 0:\n",
    "                return False\n",
    "            dec_map = defaultdict(int)\n",
    "            for i in todol:\n",
    "                linked = m1.get(i, [])\n",
    "                for j in linked:\n",
    "                    dec_map[j] += 1\n",
    "            for i in dec_map:\n",
    "                cur_v = m2.get(i, -1)\n",
    "                if cur_v == -1:\n",
    "                    continue\n",
    "                st.remove((cur_v, i))\n",
    "                newv = cur_v - dec_map[i]\n",
    "\n",
    "                st.add((newv, i))\n",
    "                m2[i] = newv\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            g[e[0]].append(e[1])\n",
    "\n",
    "        vs = [False for _ in range(n)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if vs[cur] == True: return False\n",
    "            if cur == destination: return True\n",
    "            if len(g[cur]) == 0: return False\n",
    "\n",
    "            vs[cur] = True\n",
    "            for gg in g[cur]:\n",
    "                if dfs(gg) == False: return False\n",
    "            vs[cur] = False\n",
    "            return True\n",
    "\n",
    "        if len(g[destination]) != 0: return False\n",
    "        return dfs(source)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        grap=[[] for i in range(n)]\n",
    "        for x,y in edges:\n",
    "            grap[x].append(y)\n",
    "        visited=set()\n",
    "        visited.add(source)\n",
    "        @cache\n",
    "        def dfs(p):\n",
    "            if p==destination:\n",
    "                if grap[p]==[]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            nxs=grap[p]\n",
    "            if len(nxs)==0:return False\n",
    "            for nx in nxs:\n",
    "                if nx not in visited:\n",
    "                    visited.add(nx)\n",
    "                    if dfs(nx)==False:\n",
    "                        return False\n",
    "                    visited.remove(nx)\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        return dfs(source)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            s, t = edge\n",
    "            if t not in graph[s]:\n",
    "                graph[s].add(t)\n",
    "\n",
    "        memory = set()\n",
    "        def dfs(node, path):\n",
    "            if len(graph[node]) == 0:\n",
    "                return node == destination\n",
    "            if node in memory:\n",
    "                return True\n",
    "            \n",
    "            path.add(node)\n",
    "            for succ in graph[node]:\n",
    "                if succ in path or not dfs(succ, path):\n",
    "                    return False\n",
    "            path.remove(node)\n",
    "            memory.add(node)\n",
    "            return True\n",
    "            \n",
    "        \n",
    "        return dfs(source, set([]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for src, dst in edges:\n",
    "            graph[src].append(dst)\n",
    "\n",
    "        # 判断cur的所有路径是否都能到达destination\n",
    "        cache = [False for _ in range(n)]\n",
    "        def dfs(cur, visited):\n",
    "            if cache[cur]:\n",
    "                return True\n",
    "            if not graph[cur]:\n",
    "                return cur == destination\n",
    "            visited.add(cur)\n",
    "            for nxt in graph[cur]:\n",
    "                if nxt in visited or not dfs(nxt, visited):\n",
    "                    return False\n",
    "            visited.remove(cur)\n",
    "            cache[cur] = True\n",
    "            return True\n",
    "        \n",
    "        return dfs(source, set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        def build(edges):\n",
    "            graph = [[] for _ in range(n)]\n",
    "            for edge in edges:\n",
    "                graph[edge[0]].append(edge[1])\n",
    "            return graph\n",
    "\n",
    "        def traverse(source):\n",
    "            if len(graph[source]) == 0:\n",
    "                return source == destination\n",
    "            visited[source] = True\n",
    "            onPath[source] = True\n",
    "            for elem in graph[source]:\n",
    "                if (onPath[elem]) or (not visited[elem] and not traverse(elem)):\n",
    "                    return False\n",
    "            onPath[source] = False\n",
    "            return True\n",
    "\n",
    "        graph = build(edges)\n",
    "        visited = [False]*n\n",
    "        onPath = [False]*n\n",
    "        return traverse(source)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph_rev = collections.defaultdict(list)\n",
    "        depended = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph_rev[v].append(u)\n",
    "            depended[u] += 1\n",
    "        if depended[destination]:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if i != destination and depended[i] == 0:\n",
    "                depended[i] += 1\n",
    "        def dfs(u):\n",
    "            if u == source:\n",
    "                return True\n",
    "            else:\n",
    "                for v in graph_rev[u]:\n",
    "                    depended[v] -= 1\n",
    "                    if not depended[v]:\n",
    "                        if dfs(v):\n",
    "                            return True\n",
    "                return False\n",
    "        return dfs(destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        accessable = [False for i in range(n)]\n",
    "        loops = set([destination])\n",
    "        queue_cur = [[source, []]]\n",
    "        queue_next = []\n",
    "        visited = set()\n",
    "\n",
    "        cur_next_dict = defaultdict(set)\n",
    "\n",
    "        for cur, nxt in edges:\n",
    "            cur_next_dict[cur].add(nxt)\n",
    "\n",
    "        while queue_cur or queue_next:\n",
    "            # print(queue_cur)\n",
    "            for node, history in queue_cur:\n",
    "                if node in history:\n",
    "                    print(history)\n",
    "                    return False\n",
    "\n",
    "                if node == destination:\n",
    "                    accessable[node] = True\n",
    "                    for n in history:\n",
    "                        accessable[n] = True\n",
    "                \n",
    "                if node in visited:\n",
    "                    loops.add(node)\n",
    "                    continue\n",
    "\n",
    "                visited.add(node)\n",
    "                if node != destination and node not in cur_next_dict:\n",
    "                    return False\n",
    "\n",
    "                for next_node in cur_next_dict[node]:\n",
    "                    queue_next.append([next_node, history + [node]])\n",
    "\n",
    "            queue_cur =queue_next\n",
    "            queue_next = []\n",
    "\n",
    "        for n in loops:\n",
    "            if not accessable[n]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "        if g[destination]:\n",
    "            return False\n",
    "        seen = set()\n",
    "\n",
    "        def find_sub_graph(node):\n",
    "            seen.add(node)\n",
    "            for nxt in g[node]:\n",
    "                if nxt not in seen:\n",
    "                    find_sub_graph(nxt)\n",
    "        \n",
    "        find_sub_graph(source)\n",
    "        if destination not in seen:\n",
    "            return False\n",
    "        new_g = [set() for _ in range(n)]\n",
    "        deg_in = [0] * n \n",
    "        for a, b in edges:\n",
    "            if a in seen:\n",
    "                if b not in new_g[a]:\n",
    "                    deg_in[b] += 1\n",
    "                new_g[a].add(b)                \n",
    "        tot = len(seen)\n",
    "        dq = deque([source])\n",
    "        while dq:\n",
    "            a = dq.popleft()\n",
    "            for nxt in new_g[a]:\n",
    "                deg_in[nxt] -= 1\n",
    "                if deg_in[nxt] == 0:\n",
    "                    dq.append(nxt)\n",
    "        if sum(deg_in):\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            if node == destination:\n",
    "                return True\n",
    "            if not new_g[node]:\n",
    "                return False \n",
    "            res = True \n",
    "            for nxt in new_g[node]:\n",
    "                res = res and dfs(nxt)\n",
    "            return res \n",
    "        \n",
    "        return dfs(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        return self.answer_1(n, edges, source, destination)\n",
    "\n",
    "    def answer_1(self, n, edges, source, destination):\n",
    "        graph = defaultdict(list)\n",
    "        depended = defaultdict(int)\n",
    "\n",
    "        for in_, out_ in edges:\n",
    "            graph[out_].append(in_)\n",
    "            depended[in_] += 1\n",
    "\n",
    "        if depended[destination]:\n",
    "            return False\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i!=destination and depended[i] == 0:\n",
    "                depended[i] +=1\n",
    "\n",
    "        def dfs(u):\n",
    "            if u == source:\n",
    "                return True\n",
    "\n",
    "            for v in graph[u]:\n",
    "                depended[v] -= 1\n",
    "                if not depended[v]:\n",
    "                    if dfs(v):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(destination)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
